Introducere

Reprezentarea datelor sub forma de retea e o abordare diferita fata de modul clasic de reprezentare, cel tabelar. Acest format poate evidentia noi caracteristici ale datelor si imbunatesteste vizualizarea acestora intr-un mod semnificativ. Pentru a realiza o analiza originala, setul de date folosit reprezinta structura unei retele de trafic cu tigari de contrabanda din Romania, datele fiind extrase dintr-un dosar penal. Astfel, utilizand metode de graph mining vom realiza o analiza asupra structurii retelei, dar si asupra rolurilor individuale ale membrilor.

Capitolul 1: Modelarea datelor in R

Datele au fost modelate folosind un obiect de tip reţea din librăria statnet. Legăturile dintre noduri au fost introduse folosind o lista de muchii, iar nodurile au următoarele atribute : nume, nume abreviat si rol.

netmat <- rbind(c(1,2),
                c(1,3),
                c(2,3),
                c(1,4),
                c(5,6),
                c(7,8),
                c(5,7),
                c(5,8),
                c(5,9),
                c(6,7),
                c(6,8),
                c(6,9),
                c(5,10),
                c(6,10),
                c(11,12),
                c(11,13),
                c(13,14),
                c(14,19),
                c(13,19),
                c(14,1),
                c(19,15),
                c(19,16),
                c(19,17),
                c(19,18),
                c(12,15),
                c(12,16),
                c(12,17),
                c(12,18),
                c(20,8),
                c(20,9),
                c(21,8),
                c(21,9),
                c(3,8),
                c(3,9),
                c(1,8),
                c(1,9))


net <- network(netmat, matrix.type="edgelist")

Pentru a ne asigura ca graful este unul ne-orientat, simetrizam matricea de adiacenta asociata primului obiect, si generam un nou obiect, pentru a lucra cu un graf ne-orientat. Acest lucru se datoreaza faptului ca relatiile sociale in cadrul acestei retele nu pot fi uni-directionale.

netmatsym <- symmetrize(as.sociomatrix(net), rule ="weak")


netsym <- network(netmatsym, matrix.type="adjacency")
network.vertex.names(netsym) <- c("B***cu L***na", 
                                  "B***cu An***us", 
                                  "B**scu C***nel",
                                  "B**hiu G***ge",
                                  "M**tu M**na",
                                  "Ma**u I***he",
                                  "T**a F**p",
                                  "T**a G***ghe",
                                  "S**m An**la",
                                  "G**ca G****ghe",
                                  "C**u I**n",
                                  "M***u L**do",
                                  "D**a D**a",
                                  "D**a C**l",
                                  "N**cu P**u",
                                  "N**se T**er",
                                  "S***an C***tin",
                                  "O***u A**ei",
                                  "D**a I***l",
                                  "P**ci V***e",
                                  "D***mir R**a")
set.vertex.attribute(netsym, "role", c("C", 
                                       "C", 
                                       "C",
                                       "CR",
                                       "C",
                                       "C",
                                       "CT",
                                       "CT",
                                       "CT",
                                       "C",
                                       "C",
                                       "A",
                                       "A",
                                       "C",
                                       "C",
                                       "C",
                                       "C",
                                       "C",
                                       "CT",
                                       "D",
                                       "D"))
# C : Comerciant, CR : Cartita, CT: contrabandist, A: aducator clienti, D: depozitare
set.vertex.attribute(netsym, "abrev_name", c("BL", 
                                             "BA",
                                             "BC",
                                             "BG",
                                             "MM",
                                             "MI",
                                             "TF",
                                             "TG",
                                             "SA",
                                             "GG",
                                             "CI",
                                             "ML",
                                             "DD",
                                             "DC",
                                             "NP",
                                             "NT",
                                             "SC",
                                             "OA",
                                             "DI",
                                             "PV",
                                             "DR"))

Extragerea atributelor retelei in variabile separate, pentru a fi folosite ulterior in operatiile de plotare.

netsym %v% "alldeg" <- degree(netsym)
namelab <- get.vertex.attribute(netsym, "vertex.names")
rolelab <- get.vertex.attribute(netsym, "role")
abrevnamelab <-get.vertex.attribute(netsym, "abrev_name")
my_pal <- brewer.pal(5,"Dark2")
rolecat <- as.factor(get.vertex.attribute(netsym,"role"))

Un prim plot al retelei pentru a vizualiza structura acesteia, si impartirea membrilor pe roluri.

plot(netsym,
     main = "Infractional network",
     usearrows=FALSE, 
     mode="fruchtermanreingold", 
     vertex.col = my_pal[rolecat],
     label=rolelab,
     displaylabels=T,
     vertex.cex = 1.5)

Capitolul 2: Analiza primara a retelei

O prima analiza asupra retelei este realizarea rezumatului in 5 puncte. Functiile prezente in libraria statnet faciliteaza realizarea acesteia. Analizand aceste valori, putem avea o prima impresie despre structura retelei si despre modul de organizarea a acesteia.

print("BASIC CHARACTERISTICS")
## [1] "BASIC CHARACTERISTICS"
summary(netsym, print.adj = FALSE)
## Network attributes:
##   vertices = 21
##   directed = TRUE
##   hyper = FALSE
##   loops = FALSE
##   multiple = FALSE
##   bipartite = FALSE
##  total edges = 72 
##    missing edges = 0 
##    non-missing edges = 72 
##  density = 0.1714286 
## 
## Vertex attributes:
## 
##  abrev_name:
##    character valued attribute
##    attribute summary:
##    the 10 most common values are:
## BA BC BG BL CI DC DD DI DR GG 
##  1  1  1  1  1  1  1  1  1  1 
## 
##  alldeg:
##    numeric valued attribute
##    attribute summary:
##    Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
##   2.000   4.000   6.000   6.857  10.000  14.000 
## 
##  role:
##    character valued attribute
##    attribute summary:
##  A  C CR CT  D 
##  2 12  1  4  2 
##   vertex.names:
##    character valued attribute
##    21 valid vertex names
## 
## No edge attributes
print("Size:")
## [1] "Size:"
print(network.size(netsym))
## [1] 21
print("Density:")
## [1] "Density:"
print(gden(netsym))
## [1] 0.1714286
print("Components:")
## [1] "Components:"
print(components(netsym))
## [1] 1
print("Diameter:")
## [1] "Diameter:"
gd <- geodist(netsym)
print(max(gd$gdist))
## [1] 7
print("Transitivity:")
## [1] "Transitivity:"
print(gtrans(netsym, mode="graph"))
## [1] 0.25

Capitolul 3: Managementul datelor atribuite unei retele

Folosind atributele definite în momentul creării, putem filtra reţeua astfel încat putem evidenţia importanţa unui anume rol. Spre exemplu, dacă am păstra în reţea doar Comercianţii, putem observa că aceştia sunt în mare partea izolaţi, distrugând aspectul de reţea compactă. Acest lucru evidenţiază rolul contrabandiştilor în reţea, aceştia asigurând practic conexitatea reţelei.

print("Filtering networks")
print(get.vertex.attribute(netsym, "role"))
comercianti <- get.inducedSubgraph(netsym, which (netsym %v% "role"=="C"))
gplot(comercianti,displaylabels=TRUE, main="Comercianti")

delete.vertices(comercianti, isolates(comercianti))
gplot(comercianti, displaylabels = TRUE, main="Grupuri de comercianti")

4.Basic network plotting and layout

Exista mai multe moduri de a vizualiza o retea, fiecare din aceste noduri prezentand o perspectiva diferita asupra datelor. Modul de vizualizare ales este important pentru a transmite cat mai multe informatii despre retea in mod vizual.

Circle

gplot(netsym,gmode="graph",edge.col="grey75",displaylabels=T,
      vertex.cex=1.5,mode='circle',main="circle")

Eigen

gplot(netsym,gmode="graph",edge.col="grey75",displaylabels=T,
      vertex.cex=1.5,mode='eigen',main="eigen")

Random

gplot(netsym,gmode="graph",edge.col="grey75",displaylabels=T,
      vertex.cex=1.5,mode='random',main="random")

Spring

gplot(netsym,gmode="graph",edge.col="grey75",displaylabels=T,
      vertex.cex=1.5,mode='spring',main="spring")

Fruchterman-Reingold

gplot(netsym,gmode="graph",edge.col="grey75",displaylabels=T,
      vertex.cex=1.5,mode='fruchtermanreingold',main='fruchtermanreingold')

Kamada-Kawai

gplot(netsym,gmode="graph",edge.col="grey75",displaylabels=T,
      vertex.cex=1.5,mode='kamadakawai',
      main='kamadakawai')

5.Effective network graphic design

Pot fi modificate mai multe aspecte vizuale ale retelei, atat legate de noduri cat si legate de muchii, pentru a prezenta mai bine informatiile in mod vizual.

library(network)

library(intergraph)
library(igraph)

library(networkD3)

plot(netsym,vertex.cex=0.5,main="Too small nodes")

plot(netsym,vertex.cex=6,main="Too large nodes")

plot(netsym,vertex.cex=2,main="Just right node size")

Different node type

sidenum <- 3:7
rolecat <- as.factor(get.vertex.attribute(asIgraph(netsym),"role"))
plot(netsym,usearrows=FALSE,vertex.cex=4, main="Different node type",
     displaylabels=F,vertex.sides=sidenum[rolecat])

Edge coloring example

n_edge <- network.edgecount(netsym)
linecol_pal <- c("blue","red","green")
edge_cat <- sample(1:3,n_edge,replace=T)
plot(netsym,vertex.cex=1.5,vertex.col="grey25", main="Edge coloring example",
     edge.col=linecol_pal[edge_cat],edge.lwd=2)

Different edge width

widths <- c(2,6,10)
plot(netsym,vertex.cex=1.5,main="Different edge width",
     edge.lwd=1.5*widths)

Different edge type

n_edge <- network.edgecount(netsym)
edge_cat <- sample(1:3,n_edge,replace=T)
line_pal <- c(2,3,4)
gplot(netsym,vertex.cex=0.8,gmode="graph", main="Different edge type",
      vertex.col="gray50",edge.lwd=1.5,
      edge.lty=line_pal[edge_cat])

Infractional network with legend

my_pal <- brewer.pal(5,"Dark2")
rolecat <- as.factor(get.vertex.attribute(asIgraph(netsym),"role"))
plot(netsym,
     main = "Infractional network",
     usearrows=FALSE, 
     mode="fruchtermanreingold", 
     vertex.col = my_pal[rolecat],
     label=abrevnamelab,
     displaylabels=T,
     vertex.cex = 1.5)
legend("bottomleft",legend=c("Aducator clienti","Comerciant","Cartita","Contrabandist","Depozitare"),
       col=my_pal,pch=19,pt.cex=1.5,bty="n",
       title="Criminal Role")

6.Advanced Network Graphics

Exista si moduri mai avansate de a prezenta vizual o retea, folosind biblioteci care pot genera retele mai interactive.

Tkplot

#Visnetwork
library(visNetwork)
inetsym_edge <- get.edgelist(inetsym)
inetsym_edge <- data.frame(from = inetsym_edge[,1],
                         to = inetsym_edge[,2])
inetsym_nodes <- data.frame(id = as.numeric(V(inetsym)))
visNetwork(inetsym_nodes, inetsym_edge, width = "100%")

Heatmap

Heatmap este o reprezentare speciala a unei retele prin care ne este mai usor sa observam interactiunile intre diverse noduri ale retelei si cat de mult interactioneaza fiecare nod cu celelalte.

7. Actor proeminence

Putem spune ca un nod este un actor proeminent intr-o retea daca prezenta lui are un impact special asupra retelei. Urmeaza sa vedem cateva astfel de exemple. # Cutpoints

Determining the centre nodes using the degree

Determining the centre nodes using the closeness function

Determining the centre nodes using the betweenness function

Capitolul 8: Subgrupuri

Acest capitol este dedicat descoperirii subgrupurilor dintr-o retea. Acest tip de analiza are un rol foarte important, deoarece s-a observat ca in majoritatea retelelor sociale, indiferent de dimensiunea acestora, exista o tendinta de separare a actantilor in subgrupuri puternic interconectate, iar ale caror legaturi cu membrii din afara subgrupului sunt intr-un numar relativ mic. Desi pentru o retea de dimensiuni reduse nu este necesara o analiza amanuntita pentru a descoperi grupurile din cadrul unei retele, pentru dimensiuni considerabile ale retelelor, existenta subgrupurilor nu mai este atat de evidenta, iar complexitatea metodelor necesare trebuie sa fie mai mare.

Cea mai intuitiva abordare a subgrupurilor a fost de a le lega de notiunea de coeziune sociala, adica sunt considerate ca fiind subgrupuri submultimile de noduri ce contin cat mai multe conexiuni directe. In cazul retelelor care contin o componenta ce ofera informatii despre puterea unei legaturi (spre exemplu, intr-o retea de socializare putem privi relatiile de pretenie ca avand un grad determinat de frecventa de interactiune: zilnic, saptamanal, lunar, ocazional), aceasta poate fi integrata in determinarea subgrupurilor tinand cont de faptul ca legaturile mai slabe sunt folosite mai probabil pentru a conecta doua subgrupuri diferite decat pentru a conecta doua noduri din cadrul aceluiasi subgrup.

O prima abordare bazata pe notiunea de coeziune sociala, a fost de a considera subgrup doar submultimile care au conexiune intre oricare doua noduri. Mai exact, aceasta separare reprezinta de fapt, extragerea de subgrafuri complete din reteaua initiala. Un subgrup determinat prin aceasta metoda poarta denumirea de “clique”. Mai jos sunt utilizate cateva metode pentru determinarea acestora in reteaua de traficanti. Pentru a intelege mai bine rezultatele urmatoare sunt necesare doua observatii: * putem sa consideram o dimensiune minima pentru un subgrup, de regula 3 noduri, deoarece subgrupurile de dimensiune 1 si 2 nu sunt relevante (orice nod poate fi considerat un subgrup si orice doua noduri conectate pot fi considerate un subgrup). * subgrupurile formate din patru noduri cuprind (sub forma de subgraf) subgrupuri formate din trei noduri, deci are sens sa introducem notiunea de “clique” maximal (care nu mai poate fi extins prin adaugarea altor noduri).

# Determine the maximum size of a clique
clique.number(inetsym)
## [1] 4
# Determine all the cliques
cliques(inetsym, min=3)
## [[1]]
## + 3/21 vertices, named, from ece1950:
## [1] MI TF TG
## 
## [[2]]
## + 3/21 vertices, named, from ece1950:
## [1] DD DC DI
## 
## [[3]]
## + 3/21 vertices, named, from ece1950:
## [1] BL BA BC
## 
## [[4]]
## + 3/21 vertices, named, from ece1950:
## [1] BL BC SA
## 
## [[5]]
## + 3/21 vertices, named, from ece1950:
## [1] BL BC TG
## 
## [[6]]
## + 3/21 vertices, named, from ece1950:
## [1] MM MI TF
## 
## [[7]]
## + 4/21 vertices, named, from ece1950:
## [1] MM MI TF TG
## 
## [[8]]
## + 3/21 vertices, named, from ece1950:
## [1] MM MI GG
## 
## [[9]]
## + 3/21 vertices, named, from ece1950:
## [1] MM MI SA
## 
## [[10]]
## + 3/21 vertices, named, from ece1950:
## [1] MM MI TG
## 
## [[11]]
## + 3/21 vertices, named, from ece1950:
## [1] MM TF TG
# Determine the maximal cliques
maximal.cliques(inetsym, min=3)
## [[1]]
## + 3/21 vertices, named, from ece1950:
## [1] BA BL BC
## 
## [[2]]
## + 3/21 vertices, named, from ece1950:
## [1] DC DD DI
## 
## [[3]]
## + 3/21 vertices, named, from ece1950:
## [1] GG MM MI
## 
## [[4]]
## + 4/21 vertices, named, from ece1950:
## [1] TF MM TG MI
## 
## [[5]]
## + 3/21 vertices, named, from ece1950:
## [1] MM MI SA
## 
## [[6]]
## + 3/21 vertices, named, from ece1950:
## [1] BC BL TG
## 
## [[7]]
## + 3/21 vertices, named, from ece1950:
## [1] BC BL SA
# Determine the cliques with maximum size
largest.cliques(inetsym)
## [[1]]
## + 4/21 vertices, named, from ece1950:
## [1] TG MM MI TF

In majoritatea retelelor, constrangerea de a avea legaturi intre oricare doua noduri dintr-un subgrup este prea puternica, fapt ce conduce la determinarea unor subgrupuri de dimensiuni reduse, chiar si in cadrul retelelor foarte mari. Astfel, a fost introdusa notiunea de “k-Core”, care relaxeaxa cerinta legata de numarul de legaturi pe care trebuie sa le aiba un nod cu celelalte noduri din subgrup. Concret, daca extragem un k-Core, toate nodurile trebuie sa aiba gradul cel putin egal cu k. O observatie importanta este ca o analiza “1-Core” este echivalenta cu determinarea componentelor conexe din cadrul unui graf. In cele ce urmeaza sunt analizate componentele “k-Core” din cadrul retelei de traficanti.

## For each k, determine the number of nodes that are part of a k-Core (but not a (k+1)-Core, k is maximum)
coreness <- graph.coreness(inetsym)
table(coreness)
## coreness
##  1  2  3 
##  1 13  7
# Plot the network, with each node having its maximum k on it
maxCoreness <- max(coreness)
colors <- rainbow(maxCoreness)
plot(inetsym,vertex.label=coreness,vertex.color=colors[coreness],layout=layout_with_fr)

# Gradually remove the nodes that are only part of 1-Cores and 2-Cores
i1_3 <- inetsym
i2_3 <- induced.subgraph(inetsym, vids=which(coreness > 1))
i3_3 <- induced.subgraph(inetsym, vids=which(coreness > 2))
lay <- layout.fruchterman.reingold(inetsym)
op <- par(mfrow=c(1,3),mar = c(3,0,2,0))
plot(i1_3,layout=lay,vertex.label=coreness,vertex.color=colors[coreness],main="All k-cores")
plot(i2_3,layout=lay[which(coreness > 1),],vertex.label=coreness[which(coreness > 1)],vertex.color=colors[coreness[which(coreness > 1)]],main="k-cores 2-3")
plot(i3_3,layout=lay[which(coreness > 2),],vertex.label=coreness[which(coreness > 2)],vertex.color=colors[coreness[which(coreness > 2)]],main="k-cores 3")

Pentru a putea realiza o comparatie intre mai multe moduri de a imparti o retea in subgrupuri, este necesara existenta unei metode de a stabili cat de potrivita este o impartire in subgrupuri. Astfel, a fost introdusa notiunea de modularitate. Modularitate este o statistica ce poate fi calculata efectuand scaderea dintre probabilitatea ca alegand o legatura din retea aceasta sa fie intre noduri din acelasi subgrup si aceeasi probabilitate calculata intr-o retea formata din aceleasi noduri, dar in care muchiile sunt distribuite in mod aleator (numarul de muchii din reteaua initiala este conservat). Prin urmare, vom incerca sa realizam o impartire in subgrupuri a retelei de traficanti folosind drept criteriu rolul fiecarui actant. Se poate observa la sfarsit ca acest criteriu nu este cel mai potrivit tinand cont de faptul ca modularitatea obtinuta este negativa.

## Computing the modularity of the clusterization method
V(inetsym)$group <- strtoi(V(inetsym)$role)
modularity(inetsym, V(inetsym)$group)
## [1] -0.1508488
## Visualizing the network by emphasizing the role of each node
colors <- brewer.pal(5,"Dark2")
V(inetsym)$color <- colors[strtoi(V(inetsym)$role)]
op <- par(mfrow=c(1,1))
plot(inetsym,vertex.color=V(inetsym)$color,vertex.size=20)

Pana in acest moment, metodele prezentate (“clique” si “k-Core”) exploreaza doar legaturile interne din cadrul unui subgrup, nefiind analizate tipare ale legaturilor catre exteriorul unui subgrup. De aceea, au fost dezvoltati diversi algoritmi care sa exploreze aceasta zona. In cele ce urmeaza vom folosi mai multi algoritmi de acest tip, denumiti “Community Detection”, pentru a analiza rezultatele acestora pe reteaua de traficanti, precum si pentru a compara intre ele aceste rezultate (intre unii algoritmi se poate observa o similitudine in rezultate, data si de constructia similara a acestora).

## Applying multiple community detection algorithms
cw <- cluster_walktrap(inetsym)
modularity(cw); membership(cw)
## [1] 0.4903549
## BL BA BC BG MM MI TF TG SA GG CI ML DD DC NP NT SC OA DI PV DR 
##  3  3  3  3  2  2  2  2  2  2  1  1  1  1  1  1  1  1  1  2  2
ceb <- cluster_edge_betweenness(inetsym)
modularity(ceb); membership(ceb)
## [1] 0.4903549
## BL BA BC BG MM MI TF TG SA GG CI ML DD DC NP NT SC OA DI PV DR 
##  1  1  1  1  2  2  2  2  2  2  3  3  3  3  3  3  3  3  3  2  2
cs <- cluster_spinglass(inetsym)
modularity(cs); membership(cs)
## [1] 0.4903549
## BL BA BC BG MM MI TF TG SA GG CI ML DD DC NP NT SC OA DI PV DR 
##  1  1  1  1  2  2  2  2  2  2  3  3  3  3  3  3  3  3  3  2  2
cfg <- cluster_fast_greedy(inetsym)
modularity(cfg); membership(cfg)
## [1] 0.4695216
## BL BA BC BG MM MI TF TG SA GG CI ML DD DC NP NT SC OA DI PV DR 
##  1  1  1  1  3  3  3  3  1  3  2  2  2  2  2  2  2  2  2  1  1
clp <- cluster_label_prop(inetsym)
modularity(clp); membership(clp)
## [1] 0.4409722
## BL BA BC BG MM MI TF TG SA GG CI ML DD DC NP NT SC OA DI PV DR 
##  1  1  1  1  1  1  1  1  1  1  2  2  2  2  2  2  2  2  2  1  1
cle <- cluster_leading_eigen(inetsym)
modularity(cle); membership(cle)
## [1] 0.464892
## BL BA BC BG MM MI TF TG SA GG CI ML DD DC NP NT SC OA DI PV DR 
##  1  1  1  1  3  3  3  3  1  3  2  2  2  2  2  2  2  2  2  3  3
cl <- cluster_louvain(inetsym)
modularity(cl); membership(cl)
## [1] 0.4903549
## BL BA BC BG MM MI TF TG SA GG CI ML DD DC NP NT SC OA DI PV DR 
##  3  3  3  3  1  1  1  1  1  1  2  2  2  2  2  2  2  2  2  1  1
# Comparing the community detection algorithms
table(V(inetsym)$role,membership(cw))
##    
##     1 2 3
##   1 2 0 0
##   2 6 3 3
##   3 0 0 1
##   4 1 3 0
##   5 0 2 0
compare(as.numeric(factor(V(inetsym)$role)),cw,method="adjusted.rand")
## [1] 0.02816901
compare(cw,ceb,method="adjusted.rand")
## [1] 1
compare(cw,cs,method="adjusted.rand")
## [1] 1
compare(cw,cfg,method="adjusted.rand")
## [1] 0.7075812
# Visualizing the splitting made by each method
op <- par(mfrow=c(3,2),mar=c(3,0,2,0))
plot(ceb, inetsym,vertex.label=NA,main="Edge Betweenness")
plot(cfg, inetsym,vertex.label=NA,main="Fastgreedy")
plot(clp, inetsym,vertex.label=NA,main="Label Propagation")
plot(cle, inetsym,vertex.label=NA,main="Leading Eigenvector")
plot(cs, inetsym,vertex.label=NA,main="Spinglass")
plot(cw, inetsym,vertex.label=NA,main="Walktrap")

Capitolul 10: Modele de retele aleatoare

In analiza unei retele moderne sociale se desting urmatoarele caracterisici:

  1. Este motivata de intelegerea intuitiva a structurii retelei bazata pe legaturile dintre actanti

  2. Are la baza date empirice extrase intr-un mod sistematic

  3. Se bazeaza foarte mult pe vizualizarea datelor utilizand metode grafice

  4. Depinde de utilizarea modelelor matematice si computationale

Analizele prezentate pana in acest moment au pus accent pe primele trei concepte, iar in cele ce urmeaza il vom aborda pe cel din urma. Mai precis, vom incerca in continuare sa utilizam diferite modele pentru a genera o retea care sa aiba caracteristici similare cu reteaua initiala (cea a traficantilor).

O prima abordare luata in considerare, este propusa de Paul Erdos si Alfred Renyi. In aceasta metoda, reteaua este generata pornind de la un specificat de noduri si adaugand, in mod aleator, un numar specificat de muchii. Datorita acestei constructii, acest model este referit si sub denumirea de “random graph model”. Alternativ, pentru constructia unui astfel de model se poate specifica in locul numarului de muchii, o probabilitate de a avea muchie intre doua noduri ale retelei. In continuare, este prezentat codul pentru generarea retelei utilizand cele doua metode si vizualizarea grafica a rezultatelor comparativ cu reteaua initiala.

## Generate a similar network using Erdos-Renyi method (by specify the number of edges)
no_nodes <- length(V(inetsym))
no_edges <- length(E(inetsym))
er_net1 <- erdos.renyi.game(n=no_nodes,no_edges,type='gnm')

## Generate a similar network using Erdos-Renyi method (by specify the probability of having an edge between two nodes)
edge_prob <- no_edges / ((no_nodes-1)*no_nodes)
er_net2 <- erdos.renyi.game(n=no_nodes, edge_prob,type='gnp')

op <- par(mfrow=c(1,3))
plot(inetsym,vertex.label=NA,vertex.size=10)
plot(er_net1, vertex.label=NA, vertex.size=10)
plot(er_net2, vertex.label=NA, vertex.size=10)

Modelul prezentat anterior este unul simplu de inteles, insa din cauza generalitatii sale, nu se pot genera retele care sa aiba anumite particularitati dorite (care sunt observate la o retea obtinuta empiric). Un astfel de exemplu, este faptul ca desi dimensiunile retelelor sociale pot fi de ordinul milionelor de noduri, diametrul acestora este considerabil mai mic, fapt ce nu este foarte usor de replicat in modelul anterior. De aceea modelul “Small-World” doreste sa imbunatateasca acest lucru pornind de la o configuratie prestabilita a muchiilor retelei, urmata de o modificarea a acestora cu o anumita probabilitate. Se poate observa ca folosind probabilitatea de modificare a muchiilor cu valoare 1, configuratia initiala nu va mai conta, iar modelul va fi similar cu cel prezentat anterior. Inainte de a prezenta codul pentru generarea acestui model, vom explica cum arata configuratia initiala a retelei. Nodurile sunt asezate in cerc, iar fiecare nod este legat de k dintre cei mai apropiati vecini ai sai (atat cei din dreapta, cat si cei din stanga). In exemplu urmator vom determina acest k, tinand cont de gradul mediu al unui nod, iar pentru probabilitatea de modificarea a unei muchii vom utiliza trei valori diferite ale parametrului (0.25, 0.5, 0.75). Analizand grafic cat de similare sunt aceste retele comparativ cu cea initiala.

## Generating a similar network using Small-World Model
avg_degree <- 2*no_edges/no_nodes
ws_net1 <- watts.strogatz.game(dim=1, size=no_nodes, nei=avg_degree/2, p=.25)
ws_net2 <- watts.strogatz.game(dim=1, size=no_nodes, nei=avg_degree/2, p=.5)
ws_net3 <- watts.strogatz.game(dim=1, size=no_nodes, nei=avg_degree/2, p=.75)

## Visualizing the results
op <- par(mfrow=c(2,2))
plot(inetsym,vertex.label=NA,vertex.size=10)
plot(ws_net1, vertex.label=NA, vertex.size=10)
plot(ws_net2, vertex.label=NA, vertex.size=10)
plot(ws_net3, vertex.label=NA, vertex.size=10)

Din rezultatele grafice, se poate observa ca nici acest model nu este unul multumitor. In plus, o observatie importanta pentru cele doua modele este ca nici unul nu foloseste proprietati ale gradelor nodurilor din retea. Intr-o retea empirica, gradele nodurilor nu au o distributie apropiata de medie, existand multe noduri cu grad mic, dar si noduri cu grad considerabil mai mare decat medie (intr-o retea sociala, aceste noduri ar fi persoanele celebre din diferite domenii: actori, sportivi, politicieni, etc.). Aceasta problema este adresata in modelul de generare “Scale-Free” utilizat mai jos.

## Generate a similar network using Scale-Free Model
b_net <- barabasi.game(no_nodes, directed=FALSE)

## Visualize the result
op <- par(mfrow=c(1,2))
plot(inetsym,vertex.label=NA, vertex.size=10)
plot(b_net,vertex.label=NA, vertex.size=10)

In finalul acestui capitol, sunt prezentate statistici comparative ale retelelor generate si rezultatele observate in cadrul retelei empirice.

## Comparing random models with the empirical network
list_network <- c(er_net1, ws_net2, b_net, inetsym)
comparison_table <- data.frame(
  Name = c("Erdos-Renyi", "Small world", "Scale-free model", "Empiric network"),
  Size = c(length(V(er_net1)), length(V(ws_net2)), length(V(b_net)), length(V(inetsym))),
  Density = c(gden(asNetwork(er_net1)),gden(asNetwork(ws_net2)),gden(asNetwork(b_net)),gden(asNetwork(inetsym))),
  Avg_Degree = c(length(E(er_net1))/length(V(er_net1)),length(E(ws_net2))/length(V(ws_net2)),length(E(b_net))/length(V(b_net)),length(E(inetsym))/length(V(inetsym))),
  Transitivity = c(transitivity(er_net1), transitivity(ws_net2), transitivity(b_net), transitivity(inetsym)),
  Isolates = c(sum(degree(er_net1)==0),sum(degree(ws_net2)==0),sum(degree(b_net)==0),sum(degree(inetsym)==0))
)
comparison_table
##               Name Size   Density Avg_Degree Transitivity Isolates
## 1      Erdos-Renyi   21 0.1714286   1.714286    0.2290076        1
## 2      Small world   21 0.1000000   1.000000    0.0000000        1
## 3 Scale-free model   21 0.0952381   0.952381    0.0000000        0
## 4  Empiric network   21 0.1714286   1.714286    0.2500000        0